﻿// 0807train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>

using namespace std;


/*
 给你一个 n x n 的 方形 整数数组 matrix ，
 请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
具体来说，位置 (row, col) 的下一个元素应当是
(row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1)

示例1
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径
 */

int solve01(vector<vector<int>>& matrix)
{
	int matrix_size = matrix.size();

	if (matrix_size == 1) return matrix[0][0];

	vector<vector<int>>dynamic_vec(matrix_size, vector<int>(matrix_size,INT_MAX));

	//(row, col) 的下一个元素
	//(row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1)

	for (int col=0; col<matrix_size; col++)
	{
		dynamic_vec[0][col] = matrix[0][col];
	}

	for (int row = 1; row<matrix_size; row++)
	{
		for (int col=0; col<matrix_size; col++)
		{
			int min_prev;
			if (col==0)
			{
				min_prev = min(dynamic_vec[row - 1][col], dynamic_vec[row - 1][col + 1]);
			}
			else if (col==matrix_size-1)
			{
				min_prev= min(dynamic_vec[row - 1][col-1], dynamic_vec[row - 1][col]);
			}
			else
			{
				min_prev = min(dynamic_vec[row - 1][col - 1], dynamic_vec[row - 1][col]);
				min_prev = min(min_prev, dynamic_vec[row - 1][col + 1]);
			}

			dynamic_vec[row][col] = min_prev + matrix[row][col];
		}

	}

	//for (auto&num_vec:dynamic_vec)
	//{
	//	for (auto&num:num_vec)
	//	{
	//		cout << num << ' ';
	//	}
	//	cout << '\n';
	//}


	int result = INT_MAX;

	for (int col=0; col<matrix_size; col++)
	{
		result = min(result, dynamic_vec[matrix_size - 1][col]);
	}
	return result;
	//solve01------
}


/*
 只能向右和向下园区前进
 第一行为园区长和宽；后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观
 求从起始园区到终点园区会有多少条不同的参观路径
 输入
 第一行为园区长和宽；后面每一行表示该园区是否可以参观，0表示可以参观，1表示不能参观
 输出为不同的路径数量
 3 3
0 0 0
0 1 0
0 0 0

2
 */


void solve02(vector<vector<int>>&matrix)
{
	int row_size = matrix.size();
	int col_size = matrix[0].size();
	vector<vector<int>>dynamic_grid(row_size, vector<int>(col_size, 0));

	if (row_size == 1 || col_size==1)
	{
		cout << 1;
		return;
	}

	//第0列，只有1种
	for (int row=0; row<row_size; row++)
	{
		//1 无法到达
		if (matrix[row][0] == 1) break;
		dynamic_grid[row][0] = 1;
	}

	//第0行，只有1种
	for (int col = 0; col < row_size; col++)
	{
		//1 无法到达
		if (matrix[0][col] == 1) break;
		dynamic_grid[0][col] = 1;
	}

	//向右和向下
	//int mini_prev = min(dynamic_grid[row-1][col],dynamic_grid[row][col-1])
	//dynamic_grid[row][col]=mini_prev

	for (int row=1; row<row_size; row++)
	{
		for (int col=1; col<col_size; col++)
		{
			//1无法到达
			if (matrix[row][col] == 1) continue;

			dynamic_grid[row][col] = dynamic_grid[row - 1][col]+ dynamic_grid[row][col - 1];
		}
	}

	cout << dynamic_grid[row_size - 1][col_size - 1];
	//solve02
}


/*
 给定两个字符串，分别为字符串A与字符串B。
例如A字符串为ABCABBA，B字符串为CBABAC，可以得到下图m*n的二维数组，
定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1，映射成坐标系如下图。

从原点(0,0)到(0,A)为水平边，距离为1，从(0,A)到(A,C)为垂直边，距离为1；
假设两个字符串同一位置的两个字符相同则可以作一个斜边，如(A,C)到(B,B)最短距离为斜边，距离同样为1。
出所有的斜边如下图，(0,0)到(B,B)的距离为 1个水平边+ 1个垂直边+ 1个斜边=3。
 */

vector<vector<pair<char,char>>>GetMatrix(string &str_1, string &str_2)
{
	int col_size = str_1.size()+1;
	int row_size = str_2.size()+1;

	vector<vector<pair<char, char>>>matrix(row_size, vector<pair<char, char>>(col_size));

	matrix[0][0] = make_pair('0', '0');

	//第0行
	for (int col = 1; col < col_size; col++)
	{
		matrix[0][col] = make_pair('0', str_1[col-1]);
	}

	//第0列
	for (int row=1; row<row_size; row++)
	{
		matrix[row][0] = make_pair(str_2[row-1], '0');
	}

	for (int row=1; row<row_size; row++)
	{
		for (int col=1; col<col_size; col++)
		{
			//1列
			char char_1 = str_1[col-1];
			//2行
			char char_2 = str_2[row-1];

			matrix[row][col] = make_pair(char_1, char_2);
		}

	}

	//for (auto&mini_vec:matrix)
	//{
	//	for (auto&oh_pair:mini_vec)
	//	{
	//		cout << oh_pair.first << oh_pair.second << ' ';
	//	}
	//	cout << '\n';
	//}
	
	return matrix;
	//GetMatrix
}

void solve03(string& str_col, string& str_row)
{
	int col_size = str_col.size() + 1;
	int row_size = str_row.size() + 1;
	vector<vector<pair<char, char>>>matrix = GetMatrix(str_col, str_row);
	vector<vector<int>>dynamic_grid(row_size,vector<int>(col_size));

	dynamic_grid[0][0] = 0;
	//第0行，最短路径，[0][col-1]+1
	for (int col=1; col<col_size; col++)
	{
		dynamic_grid[0][col] = dynamic_grid[0][col-1] + 1;
	}

	//第0列，最短路径，[row-1][0]+1
	for (int row=1; row<row_size; row++)
	{
		dynamic_grid[row][0] = dynamic_grid[row - 1][0] + 1;
	}

	for (int row = 1; row<row_size; row++)
	{
		for (int col=1; col<col_size; col++)
		{
			//min([row-1][col],[row][col-1])
			int min_prev = min(dynamic_grid[row - 1][col], dynamic_grid[row][col - 1]);

			pair<char, char>curr_pair = matrix[row][col];
			if (curr_pair.first==curr_pair.second)
			{
				min_prev = min(min_prev, dynamic_grid[row - 1][col - 1]);
			}
			dynamic_grid[row][col] = min_prev + 1;
		}

	}

	cout << dynamic_grid[row_size - 1][col_size - 1];
	//solve03------
}

int main()
{
	{
		//string str_col = "ABCABBA";
		//string str_row = "CBABAC";
		string str_col, str_row;
		cin >> str_col >> str_row;

		solve03(str_col, str_row);

		return 0;
	}

	{
		//3 3
		//0 0 0
		//0 1 0
		//0 0 0 2
		//行数 列数
		int row_size, col_size;
		cin >> row_size >> col_size;
		vector<vector<int>>matrix(row_size, vector<int>(col_size, 0));
		for (int r=0; r<row_size; r++)
		{
			for (int c=0; c<col_size; c++)
			{
				cin >> matrix[r][c];
			}
		}

		//for (auto&num_vec:matrix)
		//{
		//	for (auto&num:num_vec)
		//	{
		//		cout << num << ' ';
		//	}
		//	cout << '\n';
		//}

		//vector<int>vec_1 = { 0,0,0 };
		//vector<int>vec_2 = { 0,1,0 };
		//vector<int>vec_3 = { 0,0,0 };
		//vector<vector<int>>matrix = { vec_1 ,vec_2 ,vec_3 };

		solve02(matrix);

		return 0;
	}


   //matrix = [[2,1,3],[6,5,4],[7,8,9]] 13
	vector<int>vec_1 = { 2,1,3 };
	vector<int>vec_2 = { 6,5,4 };
	vector<int>vec_3 = { 7,8,9 };
	vector<vector<int>>matrix = { vec_1 ,vec_2 ,vec_3 };

	cout << solve01(matrix);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
